#include <stdio.h>
#include <stdlib.h>
#define SIZE 5  //宏定义顺序表最大空间

typedef struct Table
{
    int *head;  // 声明一个动态数组
    int length; // 记录当前顺序表长度
    int size;   // 顺序表分配存储容量
}table;

table initTable()
{
    table t;
    t.head = (int*)malloc(SIZE * sizeof(int));
    if(t.head == NULL)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = SIZE;
    return t;
}

// 顺序表插入元素
void addTable(table* t, int index, int elem)
{
    // 判断插入位置是否合法
    if(index > t->length + 1 || index < 0)
    {
        printf("插入位置有问题！");
        return ;
    }
    if(t->length >= t->size){
        t->head = (int*)realloc(t->head, (t->size+1)*sizeof(int));
        if(t->head == NULL)
        {
            printf("存储分配失败！");
        }
        t->size++;
    }
    // 插入元素位置之后的元素逐位后移
    for(int i = t->length-1; i>=index; i--)
    {
        t->head[i+1] = t->head[i];
    }
    t->head[index] = elem;
    t->length++;
}

void delTable(table* t, int elem)
{
    int i;
    for(i=0; i<t->length; i++)
    {
        if(t->head[i] == elem)
        {
            for(int j=i; j<t->length-1; j++)
            {
                t->head[j] = t->head[j+1];
            }
            t->length--;
            return ;
        }
    }
    printf("要删除的元素不存在\n");
}

int searchTable(table* t, int elem)
{
    int i;
    for(i=0; i<t->length; i++)
    {
        if(t->head[i] == elem)
        {
            return i;
        }
    }
    return -1;
}

void updateTable(table* t, int index, int elem)
{
    if(index >= t->length)
    {
        printf("修改位置越界");
        return ;
    }
    t->head[index] = elem;
}

int main()
{
    int i;
    table t = initTable();
    // 向顺序表添加元素
    for(i=0; i<SIZE; i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("初始顺序表\n");
    // 输出顺序表中的元素
    for(i=0; i<t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("\n\n在下标3处插入元素100\n");
    table *pt = &t;
    addTable(pt, 3, 100);
    for(i=0; i<t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("\n\n删除元素2\n");
    delTable(pt, 2);
    for(i=0; i<t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("\n\n查找元素100,下标为:%d", searchTable(pt, 100));
    printf("\n\n修改下标为2的元素为2\n");
    updateTable(pt, 2, 2);
    for(i=0; i<t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("\n");
    return 0;
}
